﻿//1,leetcode  221. 最大正方形（DP）
//参考：
//https://leetcode.cn/problems/maximal-square/solution/li-jie-san-zhe-qu-zui-xiao-1-by-lzhlyle/
//https://www.acwing.com/video/1593/
class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix)
    {
        int n = matrix.size();
        int m = matrix[0].size();
        //f数组表示以坐标(i,j)为右下角的最大正方形的边长
        //由第一篇参考的图解可以推导出动态规划方程:f[i,j] = min(f[i-1][j-1], f[i-1][j], f[i][j-1]) + 1
        //细节:为了防止越界问题,为状态数组的空间多开一圈的位置
        vector<vector<int>> f(n + 1, vector<int>(m + 1, 0));
        int ret = 0; //记录当前的最大边长
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                if (matrix[i - 1][j - 1] == '1') //只有出现字符1才可能存在正方形
                {
                    f[i][j] = min(f[i - 1][j - 1], min(f[i - 1][j], f[i][j - 1])) + 1;
                    ret = max(ret, f[i][j]);
                }
            }
        }
        return ret * ret;
    }
};

//2.leetcode    228. 汇总区间（双指针）
class Solution {
public:
    vector<string> summaryRanges(vector<int>& nums)
    {
        int n = nums.size();
        vector<string> ret;
        for (int i = 0; i < n; i++) //i,j双指针控制区间,区间为[i,j),左闭右开
        {
            int j = i + 1;
            //右指针移动的条件
            while (j < n && nums[j] == nums[j - 1] + 1)
            {
                j++;
            }
            if (j == i + 1) //当右指针没有移动时
            {
                ret.push_back(to_string(nums[i]));
            }
            else //j指针会移动到最后一个满足条件元素的下一个位置
            {
                ret.push_back(to_string(nums[i]) + "->" + to_string(nums[j - 1]));
            }
            i = j - 1;  //循环时i会加1,所以这里是j-1
        }
        return ret;
    }
};

//3.摩尔投票法找众数
//(1) leetcode  169. 多数元素
class Solution {
public:
    //空间复杂度为O(1)
    //思路:用s表示当前数,记作库存;q表示库存数的数量
    //当库存数量为0时,将当前数赋给库存;
    //当库存数不为0且当前数等于库存数,则库存数数量q加1;反之减1;最后库存数一定是序列中出现次数最多的数
    int majorityElement(vector<int>& nums)
    {
        int s = 0;  //store
        int q = 0; //quantity
        for (auto x : nums)
        {
            if (x == s)  q++;
            else if (q == 0)
            {
                s = x;
                q = 1;
            }
            else  q--;
        }
        return s;
    }
};
//(2)leetcode  229. 多数元素 II
//简化版: https://leetcode.cn/problems/majority-element/
//参考: https://www.acwing.com/video/1612/
//算法:摩尔投票法; 可以扩展到大小为n的整数数组中找出其中所有出现超过 ⌊ n/k ⌋ 次的元素(需要开k-1个仓库,即一共有k-1个数满足众数要求)
//注:各个仓库中的数在变化时,先判断当前数等于仓库数的情况(对应仓库中数的数目加1),再判断仓库中是否有数
//因为如果存在多个仓库(k>2),那么颠倒判断顺序就有可能将相同的数放在不同的仓库中
class Solution
{
public:
    vector<int> majorityElement(vector<int>& nums)
    {
        int s1 = 0;
        int s2 = 0;
        int q1 = 0;
        int q2 = 0;
        //寻找满足条件的k-1个数
        //注:for循环内的分支语句一定要先判断当前数是否与仓库中的数相同,再判断仓库内是否有数!!!
        //否则相同的数可能被放在不同的仓库中(这样就统计不出所需的众数了)
        for (auto x : nums)
        {
            //先
            if (q1 && s1 == x)  q1++;  //当前数等于仓库s1的数
            else if (q2 && s2 == x)  q2++;  //当前数等于仓库s2的数
            //后
            else if (!q1) //s1仓库没数
            {
                s1 = x;
                q1 = 1;
            }
            else if (!q2)  //s2仓库没数
            {
                s2 = x;
                q2 = 1;
            }
            else
            {
                q1--;
                q2--;
            }
        }
        //找到后还需要判断是否一定满足条件
        q1 = 0;
        q2 = 0;
        for (auto x : nums)
        {
            if (s1 == x)  q1++;
            else if (s2 == x)  q2++;
        }
        vector<int> ret;
        int n = nums.size();
        if (q1 > n / 3)  ret.push_back(s1);
        if (q2 > n / 3)  ret.push_back(s2);
        return ret;
    }
};